package 中等.树;

import util.TreeNode;

/**
 * 给定一棵二叉树的根 root，请你考虑它所有 从根到叶的路径：
 * 从根到任何叶的路径。（所谓一个叶子节点，就是一个没有子节点的节点）
 * 假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都
 * 小于给定的 limit，则该节点被称之为「不足节点」，需要被删除。
 * 请你删除所有不足节点，并返回生成的二叉树的根。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths
 */
public class 根到叶路径上的不足节点_1080 {

    public static void main(String[] args) {

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node1.left = node2;
        node2.left = node3;

        sufficientSubset(node1, 9);

    }

    public static TreeNode sufficientSubset(TreeNode root, int limit) {

        // 虚拟根节点，用来删除整颗树
        TreeNode tempNode = new TreeNode(0);
        tempNode.left = root;

        dfs(tempNode, 0, limit);

        return tempNode.left;
    }

    // 后缀遍历，删除节点
    // 注意：即使到当前节点的和 >= limit ,但是经过其节点的两条路径和均 < limit
    // 当前节点也需要删除，判断的依据是，递归之前左右子节点存在一个，递归之后被全部删除，
    // 则说明通过该节点全部路径和均 < limit
    private static TreeNode dfs(TreeNode curNode, int sum, int limit) {
        if (curNode == null) return null;

        boolean hasChild = false;
        if (curNode.left != null || curNode.right != null) {
            hasChild = true;
        }

        curNode.left = dfs(curNode.left, sum + curNode.val, limit);
        curNode.right = dfs(curNode.right, sum + curNode.val, limit);

        if (curNode.left == null && curNode.right == null && sum + curNode.val < limit) {
            return null;
        }
        if (curNode.left == null && curNode.right == null && hasChild) {
            return null;
        }

        return curNode;
    }

}
